package alo.p7;


/**
 * @ClassName Heap
 * @Description 堆的声明
 * @Author Fanxc
 * @DATE 2021/3/10 10:23
 * @Version 1.0
 */
public class Heap {
    public int[] array;//堆的底层数组
    public int count;//堆中元素的个数
    public int capacity;//堆的大小
    public int heap_type;//最小堆或最大堆
    //创建堆
    public Heap(int capacity,int heap_type){
        this.heap_type=heap_type;
        this.count=0;
        this.capacity=capacity;
        this.array=new int[capacity];
    }

    //结点的双亲
    public int Parent(int i){
        if (i<=0||i>=this.count){
            return -1;
        }
        return (i-1)/2;
    }
    //结点的左孩子
    public int LeftChild(int i){
        int left=2*i+1;
        if (left>=this.count){
            return -1;
        }
        return left;
    }
    //结点的右孩子
    public int RightChild(int i){
        int right=2*i+2;
        if (right>=this.count){
            return -1;
        }
        return right;
    }
    //获取最大元素
    public int GetMaximum(){
        if (this.count==0){
            return -1;
        }
        return this.array[0];
    }
    //向下渗透
    public void PercolateDown(int i){
        int l,r,max,temp;
        l=LeftChild(i);
        r=RightChild(i);
        if (l!=-1&&this.array[l]>this.array[i]){
            max=l;
        }else {
            max=i;
        }
        if (r!=-1&&this.array[r]>this.array[max]){
            max=r;
        }
        if (max!=i){
            temp=this.array[i];
            this.array[i]=this.array[max];
            this.array[max]=temp;
        }
        //直到叶子结点结束
        if (l!=-1||r!=-1) {
            PercolateDown(max);
        }
    }
    //删除最大元素
    public int DeleteMax(){
        if (this.count==0){
            return -1;
        }
        int data=this.array[0];
        this.array[0]=this.array[count-1];
        this.count--;
        PercolateDown(0);
        return data;
    }
    //扩容
    public void ResizeHeap(){
        int[] array_old=new int[this.capacity];
        System.arraycopy(this.array,0,array_old,0,this.count);
        this.array=new int[this.capacity*2];
        if (this.capacity >= 0) System.arraycopy(array_old, 0, this.array, 0, this.capacity);
        this.capacity*=2;
    }
    //插入元素、向上渗透
    public void Insert(int data){
        int i;
        if (this.count==this.capacity){
            ResizeHeap();
        }
        this.count++;
        i=this.count-1;
        while (i>=0&&data>this.array[(i-1)/2]){
            this.array[i]=this.array[(i-1)/2];
            i=(i-1)/2;
        }
        this.array[i]=data;
    }

    //删除堆
    public void DestroyHeap(){
        this.count=0;
        this.array=null;
    }

    //堆的创建
    public void BuildHeap(Heap h,int[] A,int n){
        if (h==null){
            return;
        }
        //准备合适大小
        while (n>h.capacity){
            h.ResizeHeap();
        }
        //复制数据
        if (n >= 0) {
            System.arraycopy(A, 0, h.array, 0, n);
        }
        h.count=n;
        //堆化
        for (int i = (n-1)/2; i >=0 ; i--) {
            h.PercolateDown(i);
        }
    }

    //堆排序
    public void Heapsort(int[] A,int n){
        Heap h=new Heap(n,0);
        int old_size,temp;
        BuildHeap(h,A,n);
        old_size=h.count;
        for (int i = 0; i < n; i++) {
            temp=h.array[0];
            h.array[0]=h.array[h.count-1];
            h.array[h.count-1]=temp;
            h.count--;
            h.PercolateDown(0);
        }
        h.count=old_size;
    }
}
